#include <iostream>
using namespace std;

// 优化前的版本，空间复杂度O(n)
// 爬楼梯，给定整数n表示总共n级楼梯
// 每次爬1或2级，求不同方案的总数
int dp[100] = {0};
int climbStairs1(int n) {
    // 创建备忘录数组
    // dp[x]表示爬x级台阶的总数
    // 即数组中每个数值即为一个子问题的解
    // 初始化
    dp[0] = dp[1] = 1;
    // 逐步求解所有的子问题
    for (int i = 2; i <= n; i++)
        // 递推公式：跳到当前台阶i的方案数等于
        // 跳到i-1与i-2级台阶的方案数之和
        dp[i] = dp[i - 1] + dp[i - 2];

    // 备忘录最后一个值即为原问题的解
    return dp[n];
}

// 优化后的版本，不再需要数组，空间复杂度为O(1)
int climbStairs(int n) {
    // 用两个变量滚动计算，d1表示dp[i]，d2表示dp[i-1]
    int d1 = 1, d2 = 1;

    // 依然逐步求解所有的子问题
    for (int i = 2; i <= n; i++) {
        // 临时变量防数据丢失
        int temp = d1;
        // 递推公式：跳到当前台阶i的方案数等于
        // 跳到i-1与i-2级台阶的方案数之和
        d1 = d1 + d2;
        // 传递上一步的d1到这一步的d2
        d2 = temp;
    }

    // d1保存的是最后一次计算的结果，即问题答案
    return d1;
}

int main() {
    int n = 30;
    int ans = climbStairs(n);
    cout << "跳上30级台阶的方案总数为: " << ans << endl;
    return 0;
}